/*
 * @features: 实现的图
 * @description: 内容说明
 * @Date: 2021-09-15 17:29:34
 * @Author: judu233(769471424@qq.com)
 * @LastEditTime: 2021-09-16 15:45:14
 * @LastEditors: judu233
 */

class PriorityNode {
    key: number;
    priority: number;

    constructor(key: number, priority: number) {
        this.key = key;
        this.priority = priority;
    }
}

/**
 * A priority queue with highest priority always on top
 * This queue is sorted by priority for each enqueue
 */
class PriorityQueue {

    nodes: PriorityNode[] = [];

    /**
     * Enqueue a new node
     * @param {[type]} priority
     * @param {[type]} key     
     */
    enqueue(priority: number, key: number) {
        this.nodes.push(new PriorityNode(key, priority));
        this.nodes.sort(
            function (a, b) {
                return a.priority - b.priority;
            }
        )
    }

    /**
     * Dequeue the highest priority key
     */
    dequeue(): number {
        return this.nodes.shift().key;
    }

    /**
     * Checks if empty
     */
    empty(): boolean {
        return !this.nodes.length;
    }
}

/**
 * Computes the shortest path between two node
 */
export class Dijkstra<T> {
    infinity = 1 / 0;
    verticesMap = {};
    verticeData: Map<string, T> = new Map();

    addVertice(vertices: [string, T][]) {
        vertices.forEach(v => {
            this.verticeData.set(v[0], v[1]);
        });
    }

    /**
     * Add a new vertex and related edges
     * @param {[type]} name  [description]
     * @param {[type]} edges [description]
     */
    addEdges(name: string, edges: {}) {
        this.verticesMap[name] = edges;
    }
    /**
     * Computes the shortest path from start to finish
     * @param {[type]} start  [description]
     * @param {[type]} finish [description]
     */
    shortestPath(start: string, finish: string) {
        let nodes = new PriorityQueue(),
            distances = {},
            previous = {},
            path = [],
            smallest,
            vertex,
            neighbor,
            alt;

        //Init the distances and queues variables
        for (vertex in this.verticesMap) {
            if (vertex === start) {
                distances[vertex] = 0;
                nodes.enqueue(0, vertex);
            } else {
                distances[vertex] = this.infinity;
                nodes.enqueue(this.infinity, vertex);
            }
            previous[vertex] = null;
        }

        //continue as long as the queue haven't been emptied.
        while (!nodes.empty()) {
            smallest = nodes.dequeue();
            //we are the last node
            if (smallest === finish) {
                //Compute the path
                while (previous[smallest]) {
                    path.push(smallest);
                    smallest = previous[smallest];
                }
                break;
            }

            //No distance known. Skip.
            if (!smallest || distances[smallest] === this.infinity) {
                continue;
            }

            //Compute the distance for each neighbor
            for (neighbor in this.verticesMap[smallest]) {
                alt = distances[smallest] + this.verticesMap[smallest][neighbor];
                if (alt < distances[neighbor]) {
                    distances[neighbor] = alt;
                    previous[neighbor] = smallest;
                    nodes.enqueue(alt, neighbor);
                }
            }
        }
        //the starting point isn't in the solution & 
        //the solution is from end to start.
        // let findPath = path.concat(start).reverse();
        let findPath = path.reverse();
        return {
            path: findPath,
            data: findPath.map(path => this.verticeData.get(path))
        };
    }
}